// 动态规划，会超时

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool> > dp(s.size(), vector<bool>(s.size()));
        int maxLen = 1;
        int begin = 0;
        for (int i = 0; i < s.size(); ++i) {
            dp[i][i] = true;
        }
        for (int j = 1; j < s.size(); ++j) {
            for (int i = 0; i < s.size(); ++i) {
                // 精华，仔细体会(j - i < 3 || dp[i + 1][j - 1])这一条件
                dp[i][j] = (s[i] == s[j]) && (j - i < 3 || dp[i + 1][j - 1]);
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }   
        }
        return s.substr(begin, maxLen);
    }
};
